DP S

The question of how many natural numbers less than or equal to some number K satisfy the condition

Assumption that it is not possible to naively check K numbers because K is too big.

Digit DPs are much easier to write than DPs to receive.

I see, when I tried it before and bugged it, I was doing it with the implementation I was getting.

First, consider a simple "count up the number of natural numbers less than or equal to K" with DP

https://gyazo.com/c9063ac33df020121c1f8d9ce839578a

Counting the number of natural numbers less than or equal to 57

Includes zeros, so "57 less than 57 and 1 equal".

The first i digits are the domain, and the number of "numbers less than or equal to K" and "numbers equal to K" up to that point are the DP values.

By the way, the "number that is equal k" is always 1, so there's no need to have it in a table.

I'm wondering if there are a lot of explanations, etc., that have it in a table, and sometimes that's more convenient to implement if it's a more complex problem.

In this issue, I counted every so much divided by D to check for the additional condition "divisible by D", but in my implementation, I did not provide a table for "equal K".

code:python

def solve(N, D):

equal = 0

for digit in N:

for new_digit in range(10):

for d in range(D):

if new_digit < digit:

for d in range(D):

less = new_less

equal += digit

equal %= D

ret -= 1 # for x = 0

if equal == 0: # for x = N

ret += 1

return ret % MOD

old version

code:python

def solve(K, D):

N = len(K)

border = 0

for i in range(N):

for j in range(10):

for d in range(D):

border %= D

ret += (border == 0)

return ret % MOD

---